package leetcode101.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @class Code10
 * @description 99. 恢复二叉搜索树
 * 给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
 *
 * 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,3,null,null,2]
 * 输出：[3,1,null,null,2]
 * 解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
 * 示例 2：
 *
 *
 * 输入：root = [3,1,4,null,null,2]
 * 输出：[2,1,4,null,null,3]
 * 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-06-24 8:25
 */
public class Code10 {


    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(3);
        TreeNode right = new TreeNode(2);
        root.left = left;
        left.right = right;
        root.right = null;
        left.left = null;
        right.left = null;
        right.right = null;
        recoverTree(root);
    }

    public static void recoverTree(TreeNode root) {
        List<TreeNode> bucket = new ArrayList<>();
        dfs(root, bucket);
        int pos1, pos2;
        for (int i = 0; i < bucket.size() - 1; i++) {
            if (bucket.get(i).val > bucket.get(i + 1).val) {
                pos1 = i;
                for (pos2 = i + 1; pos2 < bucket.size(); pos2++) {
                    if (bucket.get(pos2).val < bucket.get(i).val && pos2 == bucket.size() - 1) {
                        break;
                    }
                    if (bucket.get(pos2).val > bucket.get(i).val) {
                        pos2--;
                        break;
                    }
                }
                int temp = bucket.get(pos1).val;
                bucket.get(pos1).val = bucket.get(pos2).val;
                bucket.get(pos2).val = temp;
            }
        }
    }

    private static void dfs(TreeNode root, List<TreeNode> list) { // 中序遍历
        if (root == null) {
            return;
        }
        dfs(root.left, list);
        list.add(root);
        dfs(root.right, list);
    }

}

/*
按中序遍历保存所有的结点于list中
然后遍历list找到需要交换的两个节点
 */